package com.zhaofan.other;


import org.junit.Test;

//给定两个整数，被除数 dividend 和除数 divisor。将两数相除，要求不使用乘法、除法和 mod 运算符。
//
// 返回被除数 dividend 除以除数 divisor 得到的商。
//
// 整数除法的结果应当截去（truncate）其小数部分，例如：truncate(8.345) = 8 以及 truncate(-2.7335) = -2
//
//
//
// 示例 1:
//
// 输入: dividend = 10, divisor = 3
//输出: 3
//解释: 10/3 = truncate(3.33333..) = truncate(3) = 3
//
// 示例 2:
//
// 输入: dividend = 7, divisor = -3
//输出: -2
//解释: 7/-3 = truncate(-2.33333..) = -2
//
//
//
// 提示：
//
//
// 被除数和除数均为 32 位有符号整数。
// 除数不为 0。
// 假设我们的环境只能存储 32 位有符号整数，其数值范围是 [−2³¹, 231 − 1]。本题中，如果除法结果溢出，则返回 231 − 1。
public class No29 {


    public static void main(String[] args) {
        int dividend=-1010369383,divisor=-2147483648;
        System.out.println(divide(dividend,divisor));
    }

    /**
     *
     * @param dividend 被除数
     * @param divisor 除数
     * @return
     */
    public static int divide(int dividend, int divisor) {
        if(divisor==0) return 0;
        if(divisor==-1){
            if(dividend==Integer.MIN_VALUE) return Integer.MAX_VALUE;
            else return -dividend;
        }
        int flag=1;
        if((dividend<0&&divisor>0)||(dividend>0&&divisor<0)) flag=-1;
        long a=dividend<0?-((long)dividend):dividend;
        long b=divisor<0?-((long)divisor):divisor;
        int result=div(a,b);

        return flag==1?result:(result==Integer.MAX_VALUE? Integer.MAX_VALUE:-result);
    }

    /**
     * 可以使用迭代用除数1,2,3次的往上加,但对于大数来所太满了,使用幂次会速度快很多
     * 10/2=(10-8,2)+4=()
     * @param dividend
     * @param divisor
     * @return
     */
    private static int div(long dividend, long divisor) {
        if(dividend<divisor) return 0;
        int count=1;
        long tb=divisor;//tb哟可能超出精度
        while ((tb+tb)<=dividend){
            tb+=tb;
            count+=count;//为什么这里会翻倍,tb在这里是2的N次方,所以count不能是单纯的+1
        }
        return count+div(dividend-tb,divisor);
    }
}
